#pragma once

#include <stdint.h>
#include <cassert>
#include <vector>

namespace book
{

template <typename T>
class Menu
{
public:
    Menu() {}

    Menu(const Menu &b) : root_(b.root_) {}

    Menu(Menu &&b) : root_(std::move(b.root_)) {}

    ~Menu() {
        for (Node *node : root_.children_) {
            recursiveDelete(node);
        }
    }

    Menu &operator=(const Menu &b) {
        if (this != &b) {
            root_ = b.root_;
        }
        return *this;
    }

    Menu &operator=(Menu &&b) {
        if (this != &b) {
            *this = std::move(b);
        }
        return *this;
    }

    class Node;

    class NodesView
    {
    public:
        using value_type = Node;

        class Iter
        {
        public:
            Iter(typename std::vector<Node *>::const_iterator &&it)
                : it_(std::move(it)) {}

            const Node &operator*() const {
                return *(*it_);
            }
            Iter &operator++() {
                ++it_;
                return *this;
            }
            bool operator!=(const Iter &b) const {
                return it_ != b.it_;
            }

        private:
            typename std::vector<Node *>::const_iterator it_;
        };

        using const_iterator = Iter;
        using iterator = Iter;

        const_iterator begin() const {
            return const_iterator(nodes_.begin());
        }

        const_iterator end() const {
            return const_iterator(nodes_.end());
        }

        bool empty() const {
            return nodes_.empty();
        }

    private:
        NodesView(const std::vector<Node *> &nodes)
            : nodes_(nodes) {}

    private:
        const std::vector<Node *> &nodes_;

        friend class Node;
    };

    class Node
    {
    public:
        Node() {}

        Node(Node &&b) {
            *this = std::move(b);
        }

        Node(int32_t level, const T &data)
            : level_(level), data_(data) {
        }

        Node(const T &data): data_(data) {
        }

        const T &data() const {
            return data_;
        }

        T &data() {
            return data_;
        }

        void setData(const T &data) {
            data_ = data;
        }

        NodesView children() const {
            return NodesView(children_);
        }

        void addChild(Node &&child) {
            Node *newNode = new Node;
            *newNode = std::move(child);
            children_.push_back(newNode);
        }

    private:
        Node(const Node &b) {
            *this = b;
        }
 
        Node &operator=(const Node &b) {
            if (this != &b) {
                level_ = b.level_;
                deep_ = b.deep_;
                if (parent_) {
                    parent_->removeChild(this);
                }
                parent_ = nullptr; // do not set parent here
                data_ = b.data_;

                for (Node *c : children_) {
                    delete c;
                }

                for (const Node *src : b.children_) {
                    Node *dest = new Node;
                    *dest = *src;
                    children_.push_back(dest);
                    dest->parent_ = this;
                }
            }
            return *this;
        }

        Node &operator=(Node &&b) {
            if (this != &b) {
                level_ = b.level_;
                b.level_ = 0;
                deep_ = b.deep_;
                b.deep_ = 0;
                parent_ = nullptr; // do not set parent here
                if (b.parent_) {
                    b.parent_->removeChild(&b);
                }
                data_ = std::move(b.data_);
                for (Node *c : children_) {
                    delete c;
                }
                children_ = std::move(b.children_);
                for (Node *c : children_) {
                    c->parent_ = this;
                }
            }
            return *this;
        }

        void removeChild(Node *child) {
            const auto end = children_.end();
            for (auto it = children_.begin(); it != end; ++it) {
                if (*it == child) {
                    children_.erase(it);
                    return;
                }
            }
        }

        void setParent(Node *parent) {
            parent_ = parent;
        }

        Node *parent() {
            return parent_;
        }

        void addChild(Node *child) {
            children_.push_back(child);
            child->setParent(this);
            child->deep_ = deep_ + 1;
        }

        bool hasChild() const {
            return !children_.empty();
        }

    private:
        int32_t level_ = 0; // 构建目录时由外部指定的层级
        int32_t deep_ = 0; // 节点在目录中的实际层级，有效的最高层级为1，连续递增
        Node *parent_ = nullptr;
        std::vector<Node *> children_;

        T data_;

        friend class Builder;
        friend class Menu;
    };

    class Builder
    {
    public:

        Builder(Menu &menu)
            : menu_(menu) {
        }

        void add(int32_t level, const T &data) {
            if (menu_.root_.hasChild()) {
                Node *latest = findLatestNode();
                insertNode(latest, level, data);
            } else {
                latestNodeCache_ = new Node(level, data);
                menu_.root_.addChild(latestNodeCache_);
            }
        }

    private:
        Node *findLatestNode() {
            if (latestNodeCache_) {
                return latestNodeCache_;
            } else {
                assert(menu_.root_.hasChild());
                return findLatestNodeRecursive(menu_.root_.children_.back());
            }
        }

        static Node *findLatestNodeRecursive(Node *node) {
            if (!node->hasChild()) {
                return node;
            } else {
                return findLatestNodeRecursive(node->children_.back());
            }
        }

        void insertNode(Node *latest, int32_t level, const T &data) {
            if (level == latest->level_) {
                latestNodeCache_ = new Node(level, data);
                latest->parent_->addChild(latestNodeCache_);
                return;
            }

            if (level > latest->level_) {
                latestNodeCache_ = new Node(level, data);
                latest->addChild(latestNodeCache_);
                return;
            }

            Node *n = latest->parent_;
            while (true) {
                if (isRoot(n) || n->level_ < level) {
                    latestNodeCache_ = new Node(level, data);
                    n->addChild(latestNodeCache_);
                    return;
                }
                n = n->parent_;
            }

            assert(false); // never reach here
        }

        static bool isTop(Node *node) {
            return isRoot(node->parent_);
        }

        static bool isRoot(Node *node) {
            return node->parent_ == nullptr;
        }

    private:
        Menu &menu_;
        Node *latestNodeCache_ = nullptr;
    };

    Menu(Node &&node) {
        root_ = std::move(node);
    }

    NodesView items() const {
        return NodesView(root_.children());
    }

private:
    static void recursiveDelete(Node *node) {
        assert(node);
        for (Node *child : node->children_) {
            recursiveDelete(child);
        }
        delete node;
    }

private:
    Node root_;
};

} // namespace book
